'''
https://leetcode.cn/problems/strobogrammatic-number/description/
https://leetcode.cn/problems/strobogrammatic-number-ii
'''

from typing import List


class Solution:
    def isStrobogrammatic(self, num: str) -> bool:
        strobogrammatic_pairs = {'0': '0', '1': '1', '6': '9', '8': '8', '9': '6'}
        left, right = 0, len(num) - 1
        while left <= right:
            if num[left] not in strobogrammatic_pairs or num[right] != strobogrammatic_pairs[num[left]]:
                return False
            left += 1
            right -= 1
        return True
        
    def findStrobogrammatic(self, n: int) -> List[str]:
        pairs = {"0": "0", "1": "1", "6": "9", "8": "8", "9": "6"}
        def f(n, is_head):
            if n == 0:
                return ['']
            if n == 1:
                return ['0', '1', '8']
            mids = f(n-2, False)
            res = []
            for k, v in pairs.items():
                if k == '0' and is_head:
                    continue
                for mid in mids:
                    res.append(k + mid + v)
            return res
        return f(n, True)